#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

void debug(const char* s){
	return;
	cout<<s;
}

char* substr(const char* str,int st,int len){
	char* ret=(char*)malloc(len+1);
	int i=0;
	while(i<len){
		ret[i++]=str[st+i];
	}
	ret[len]='\0';
	return ret;
}

typedef struct ll{
	string name;
	int range;
	int length;
	bool sorted;
	bool unique;
}Lot;
	
class Lottery{
public:
	vector<string>* sortByOdds(vector<string>& lot);
	Lot* parse_lot(const string& str);
	void printLot(const Lot * l);
	unsigned long long calc_lot(const Lot * l);
};

unsigned long long Lottery::calc_lot(const Lot * l){
	unsigned long long ret=0;
	int s=l->range - l->length +1;
	unsigned long long a=1;
	for(int i=0; i<l->length ;i++)
		a*=(l->range-i);
	
	if(l->unique && ! l->sorted){
		return a;
	}
	
	unsigned long long b=1;
	for(int i=1; i < l->length+1 ;i++) b=b*i;
	
	unsigned long long same=a/b;
	
	cout<<a<<","<<b<<","<<l->length<<"\n";
	if(l->unique && l->sorted){
		return same;
	}
	
	unsigned long long c=1;
	for(int i=0;i<l->length;i++){
		c*=l->range;
	}
	
	if(! l->unique && !l->sorted){
		return c;
	}
	
	
	unsigned long long d=1;
	for(int i=0;i<l->length;i++){
		d=d*l->length;
	}
	
	if(! l->unique && l->sorted){		
		return c-same;
		
	}
	return ret;
}
	
void Lottery::printLot(const Lot* l){
	cout<<l->name<<": "<<l->range<<" "<<l->length<<" "<<l->sorted<<" "<<l->unique<<"\n";
}

Lot* Lottery::parse_lot(const string& str){
	debug("parse");
	const char* ss=str.c_str();
	Lot* l=new Lot();
	
	//Lot* l=(Lot*)malloc(sizeof(Lot));
	int i=0;
	int n=i;
	int len=str.length();
	while(str[i]!=':' && i<len){
		i++;
	}
	assert(i>0 && i<len && str[i]==':');
	l->name=string(str,0,i-1+1);
	i+=2;
	n=i;
	while(str[i]!=' ')i++;
	char* s=substr(ss,n,i-n);
	//cout<<"note this"<<str[n]<<" " <<i-n<<"\t";
	l->range=atoi(s);
	free(s);
	n=i+1;
	i++;
	while(str[i]!=' ')i++;
	s=substr(ss,n,i-n);
	l->length=atoi(s);
	free(s);
	i++;
	l->sorted=(str[i]=='T'?true:false);
	i+=2;
	l->unique=(str[i]=='T'?true:false);
	
	debug("parse end");
	return l;
}

vector<string>* Lottery::sortByOdds(vector<string>& lot){
	vector<string>* v=new vector<string>();
	if(lot.size()==0){
		return v;
	}
	map<string,unsigned long long> result;
	multimap<unsigned long long,string> mm;
	typedef multimap<unsigned long long,string,less<unsigned long long> >::value_type mmvt;
	typedef multimap<unsigned long long,string,less<unsigned long long> >::const_iterator mitt;
		
	vector<Lot*> lots;
	for(int i=0;i<lot.size();i++){
		Lot* l=parse_lot(lot[i]);
		lots.push_back(l);
		printLot(l);
		result[l->name]=calc_lot(l);
		mm.insert( mmvt(calc_lot(l),l->name) );
		cout<<l->name<<" = "<<result[l->name]<<"\n";
	}
	mitt mit;
	mit=mm.begin();
	while(mit!=mm.end()){
		cout<<mit->first<<" "<<mit->second<<"\n";
		mit++;
	}
}


int main(){
	vector<string> v(4);
	v[0]="PICK ANY TWO: 10 2 F F";
	v[1]="PICK TWO IN ORDER: 10 2 T F";
	v[2]="PICK TWO DIFFERENT: 10 2 F T";
	v[3]="PICK TWO LIMITED: 10 2 T T";
	
	Lottery l;
	l.sortByOdds(v);
	
	assert(l.calc_lot(l.parse_lot(v[1]))==55);
	vector<string> v2(7);
	v2[0]="INDIGO: 93 8 T F";
	v2[1]="ORANGE: 29 8 F T";
	v2[2]="VIOLET: 76 6 F F";
	v2[3]="BLUE: 100 8 T T";
	v2[4]="RED: 99 8 T T";				
	v2[5]="GREEN: 78 6 F T";	
	v2[6]="YELLOW: 75 6 F F";
	
	l.sortByOdds(v2);
}
